#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 189. 轮转数组
class Solution1
{
public:
    void rotate(vector<int>& nums, int k) 
    {
        int n = nums.size();
        k %= n;
        reverse(nums.begin(), nums.begin() + n - k);
        reverse(nums.begin() + n - k, nums.end());
        reverse(nums.begin(), nums.end());
    }
};

// 238. 除自身以外数组的乘积
class Solution2
{
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> ret(n);
        ret[0] = 1;
        for(int i = 1; i < n; ++i) ret[i] = ret[i - 1] * nums[i - 1];

        int right = 1;
        for(int i = n - 1; i >= 0; --i)
        {
            ret[i] *= right;
            right *= nums[i];
        }
        return ret;
    }
};

// 41. 缺失的第一个正数
class Solution3
{
public:
    int firstMissingPositive(vector<int>& nums) 
    {
        int n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] <= 0) nums[i] = n + 1;
        }

        for(int i = 0; i < n; ++i)
        {
            int num = abs(nums[i]);
            if(num <= n) nums[num - 1] = -abs(nums[num - 1]);
        }

        for(int i = 0; i < n; ++i)
        {
            if(nums[i] > 0) return i + 1;
        }
        return n + 1;
    }
};

// 73. 矩阵置零
class Solution4
{
public:
    void setZeroes(vector<vector<int>>& matrix) 
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<bool> row(m), col(n);
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(!matrix[i][j])
                {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(row[i] || col[j]) matrix[i][j] = 0;
            }
        }
    }
};

// 54. 螺旋矩阵
class Solution5
{
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) 
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> ret(m * n);
        int left = 0, right = n - 1;
        int cur = 0, below = m - 1;
        int i = 0, j = 0;
        while(true)
        {
            for(i = left; i <= right; ++i) ret[j++] = matrix[cur][i];
            if(++cur > below) break;

            for(i = cur; i <= below; ++i) ret[j++] = matrix[i][right];
            if(left > --right) break;

            for(i = right; i >= left; --i) ret[j++] = matrix[below][i];
            if(cur > --below) break;

            for(i = below; i >= cur; --i) ret[j++] = matrix[i][left];
            if(++left > right) break;
        }

        return ret;
    }
};

// 48. 旋转图像
class Solution6
{
public:
    void rotate(vector<vector<int>>& matrix) 
    {
        int n = matrix.size();
        for(int i = 0; i < n / 2; ++i)
        {
            for(int j = 0; j < (n + 1) / 2; ++j)
            {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = tmp;
            }
        }
    }
};

// 240. 搜索二维矩阵 II
class Solution7
{
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) 
    {
        int m = matrix.size(), n = matrix[0].size();
        int row = 0, col = n - 1;
        while(row < m && col >= 0)
        {
            if(matrix[row][col] < target)
                ++row;
            else if(matrix[row][col] > target)
                --col;
            else
                return true;
        }    
        return false;
    }
};